package com.ultrapower.charts.delaunay
{
	import de.polygonal.ds.Collection;
	import de.polygonal.ds.DLinkedList;
	import de.polygonal.ds.Iterator;
	import de.polygonal.ds.Set;
/**
 * A 2D Delaunay Triangulation (DT) with incremental site insertion.
 *
 * This is not the fastest way to build a DT, but it's a reasonable way to build
 * a DT incrementally and it makes a nice interactive display. There are several
 * O(n log n) methods, but they require that the sites are all known initially.
 *
 * A Triangulation is a Set of Triangles. A Triangulation is unmodifiable as a
 * Set; the only way to change it is to add sites (via delaunayPlace).
 *
 * @author Paul Chew
 *
 * Created July 2005. Derived from an earlier, messier version.
 *
 * Modified November 2007. Rewrote to use AbstractSet as parent class and to use
 * the Graph class internally. Tried to make the DT algorithm clearer by
 * explicitly creating a cavity.  Added code needed to find a Voronoi cell.
 *
 * Translated to AS3 version by lwz7512, in Sep 2008.
 * 
 */

	public class Triangulation implements Collection
	{
		private var mostRecent:Triangle = null;      // Most recently "active" triangle
    	private var triGraph:Graph;        // Holds triangles for navigation
		
		
		public function Triangulation(triangle:Triangle)
		{
			triGraph = new Graph();
	        triGraph.add(triangle);
	        mostRecent = triangle;
		}
		
		public function clear():void{
			
		}
		public function toArray():Array{
			return triGraph.nodeSet;
		}
		
		public function contains(triangle:*):Boolean{
			var result:Boolean;
			for(var i:int;i<triGraph.nodeSet.length;i++){
				if(triangle == triGraph.nodeSet[i]){
					result = true;
					break;
				}
			}			
			return result;
		}
		public function isEmpty():Boolean{
			var result:Boolean = (triGraph.nodeSet.length==0)?true:false;
			return result;
		}
		public function toString():String{
			return "Triangulation with " + this.size + " triangles";
		}
		
		public function get size():int{
			return triGraph.nodeSet.length;
		}
		public function get iterator():Iterator{
			return new ArrayIterator(triGraph.nodeSet);
		}
		
		/**
	     * Report neighbor opposite the given vertex of triangle.
	     * @param site a vertex of triangle
	     * @param triangle we want the neighbor of this triangle
	     * @return the neighbor opposite site in triangle; null if none
	     * @throws IllegalArgumentException if site is not in this triangle
	     */
	    public function neighborOpposite (site:Pnt, triangle:Triangle):Triangle {
	        if (!triangle.contains(site))
	            throw new Error("Bad vertex; not in triangle");
	        var neighbors:ArraySet = triGraph.getNeighbors(triangle);
	        trace("find neighbors: "+neighbors.toString())
	        var neighborsIterator:Iterator = neighbors.iterator;
	        while(neighborsIterator.hasNext()){
	        	var neighborTriangle:Triangle = neighborsIterator.next() as Triangle;
	        	if(!neighborTriangle.contains(site)){
	        		return neighborTriangle;
	        	}
	        }
	        
	        return null;
	    }
	
	    /**
	     * Return the set of triangles adjacent to triangle.
	     * @param triangle the triangle to check
	     * @return the neighbors of triangle
	     */
	    public function neighbors(triangle:Triangle):ArraySet {
	        return triGraph.getNeighbors(triangle);
	    }
	
	    /**
	     * Report triangles surrounding site in order (cw or ccw).
	     * @param site we want the surrounding triangles for this site
	     * @param triangle a "starting" triangle that has site as a vertex
	     * @return all triangles surrounding site in order (cw or ccw)
	     * @throws IllegalArgumentException if site is not in triangle
	     */
	    public function surroundingTriangles (site:Pnt, triangle:Triangle):Array {
	        if (!triangle.contains(site))
	            throw new Error("IllegalArgumentException: Site not in triangle");
	        var list:Array = new Array;
	        var start:Triangle = triangle;
	        var guide:Pnt = triangle.getVertexButNot(site);        // Affects cw or ccw
	        var tempTri:Triangle = triangle;//modified	        
	        while (true) {
	        	list.push(tempTri);//modified
	            var previous:Triangle = tempTri;
	            tempTri = neighborOpposite(guide, tempTri); // Next triangle
	            guide = previous.getVertexButNot(site, guide);     // Update guide	            	
	            trace("tempTri: "+tempTri.toString()+"/start: "+start.toString());
	            if (tempTri == start) break;	            
	        }
	        return list;
	    }
	
	    /**
	     * Locate the triangle with point inside it or on its boundary.
	     * @param point the point to locate
	     * @return the triangle that holds point; null if no such triangle
	     */
	    public function locate (point:Pnt):Triangle {
	        var triangle:Triangle = mostRecent;
	        if (!this.contains(triangle)) triangle = null;
	
	        // Try a directed walk (this works fine in 2D, but can fail in 3D)
	        var visited:Set = new Set();
	        while (triangle != null) {
	            if (visited.contains(triangle)) { // This should never happen
	                trace("Warning: Caught in a locate loop");
	                break;
	            }
	            visited.setItem(triangle);
	            // Corner opposite point
	            var corner:Pnt = point.isOutside(triangle.toArray());
	            if (corner == null){
	            	 return triangle;
	            }else{
	            	triangle = neighborOpposite(corner, triangle);
	            }
	            
	        }
	        // No luck; try brute force
	       trace("Warning: Checking all triangles for " + point);
	        for each(var tri:Triangle in triGraph.nodeSet) {
	            if (point.isOutside(tri.toArray()) == null) return tri;
	        }
	        // No such triangle
	        trace("Warning: No triangle holds " + point);
	        return null;
	    }
	
	    /**
	     * Place a new site into the DT.
	     * Nothing happens if the site matches an existing DT vertex.
	     * @param site the new Pnt
	     * @throws IllegalArgumentException if site does not lie in any triangle
	     */
	    public function delaunayPlace (site:Pnt):void {
	        // Uses straightforward scheme rather than best asymptotic time
	
	        // Locate containing triangle
	        var triangle:Triangle = locate(site);
	        // Give up if no containing triangle or if site is already in DT
	        if (triangle == null)
	            throw new Error("IllegalArgumentException: No containing triangle");
	        if (triangle.contains(site)) return;
	
	        // Determine the cavity and update the triangulation
	        var cavity:Set = getCavity(site, triangle);	        
	        mostRecent = update(site, cavity);
	        trace("site placed!");
	    }
	
	    /**
	     * Determine the cavity caused by site.
	     * @param site the site causing the cavity
	     * @param triangle the triangle containing site
	     * @return set of all triangles that have site in their circumcircle
	     */
	    private function getCavity (site:Pnt, triangle:Triangle):Set {
	        var encroached:Set = new Set();
	        var toBeChecked:DLinkedList = new DLinkedList();
	        var marked:Set = new Set();
	        toBeChecked.append(triangle);
	        marked.setItem(triangle);
	        while (!toBeChecked.isEmpty()) {
	            triangle = toBeChecked.removeHead();
	            if (site.vsCircumcircle(triangle.toArray()) == 1)
	                continue; // Site outside triangle => triangle not in cavity
	            encroached.setItem(triangle);
	            // Check the neighbors
	            var neighbors:ArraySet = triGraph.getNeighbors(triangle);
	            var neibIterator:Iterator = neighbors.iterator;
	            while(neibIterator.hasNext()){
	            	var neighbor:Triangle = neibIterator.next() as Triangle;
	            	if (marked.contains(neighbor)) continue;
	                marked.setItem(neighbor);
	                toBeChecked.append(neighbor);
	            }
	           
	        }
	        return encroached;
	    }
	
	    /**
	     * Update the triangulation by removing the cavity triangles and then
	     * filling the cavity with new triangles.
	     * @param site the site that created the cavity
	     * @param cavity the triangles with site in their circumcircle
	     * @return one of the new triangles
	     */
	    private function update(site:Pnt, cavity:Set):Triangle {
	    	//Set<Set<Pnt>>
	        var boundary:Set = new Set();
	        //Set<Triangle>
	        var theTriangles:Set = new Set();
	
	        // Find boundary facets and adjacent triangles
	        var cavIterator:Iterator = cavity.iterator;
	        var cavityArr:Array = cavity.toArray();
	        while (cavIterator.hasNext()) {	        	
	        	var triangle:Triangle = cavIterator.next() as Triangle;
	            theTriangles.addAll(neighbors(triangle));
	            var triangleIterator:Iterator = triangle.iterator;
	            while(triangleIterator.hasNext()) {
	            	var vertex:Pnt = triangleIterator.next() as Pnt;
	                var facet:ArraySet = triangle.facetOpposite(vertex);
	                var containFacet:Boolean = boundary.containCollection(facet);	                
	                if (containFacet){
	                	var beforeDelBoundary:Array = boundary.toArray();
	                	boundary.removeCollection(facet);
	                }else{
	                	boundary.setItem(facet);
	                }
	                var boundaryArr:Array = boundary.toArray();
	            }
	        }
	        theTriangles.removeAll(cavity);        // Adj triangles only
	
	        // Remove the cavity triangles from the triangulation
	        var triIterator:Iterator = cavity.iterator;
	        while(triIterator.hasNext()){
	        	var ttriangle:Triangle = triIterator.next() as Triangle;
	        	triGraph.removeNode(ttriangle);
	        }
	        
	        // Build each new triangle and add it to the triangulation
	        var newTriangles:Set = new Set();	        
	        var boundaryIterator:Iterator = boundary.iterator;
	        while(boundaryIterator.hasNext()) {
	        	var vertices:ArraySet = boundaryIterator.next() as ArraySet;
	            vertices.addItem(site);
	            var tri:Triangle = new Triangle(vertices);
	            var tripnts:Array = tri.toArray();
	            triGraph.add(tri);
	            newTriangles.setItem(tri);
	        }
	
	        // Update the graph links for each new triangle
	        theTriangles.addAll(newTriangles);    // Adj triangle + new triangles
	        var newIterator:Iterator = newTriangles.iterator;
	        while(newIterator.hasNext()){
	        	var ntriangle:Triangle = newIterator.next() as Triangle;
	        	var theIterator:Iterator = theTriangles.iterator;
	        	while(theIterator.hasNext()){
	        		var other:Triangle = theIterator.next() as Triangle;
	        		if (ntriangle.isNeighbor(other)){
	        			triGraph.addLink(ntriangle, other);
	        		}	                   
	        	}	                
	        }	            
	
	        // Return one of the new triangles
	        return newTriangles.iterator.next();
	    }


		
		
		
		
		
	}//end of class
}
import de.polygonal.ds.Iterator;

internal class ArrayIterator implements Iterator
{	
	private var _a:Array;
	private var _cursor:int;
	private var _size:int;
	
	public function ArrayIterator(arr:Array)
	{		
		_a = arr;
		_cursor = 0;
		_size = _a.length;
	}
	
	public function next():*
	{
		return _a[_cursor++];
	}
	
	public function hasNext():Boolean
	{
		return _cursor < _size;
	}
	
	public function start():void
	{
		_cursor = 0;
	}

	public function get data():*
	{
		return _a[_cursor];
	}
	
	public function set data(obj:*):void
	{				
		_a[_cursor] = obj;
	}	
}